package org.example.test;

import org.example.sword2offer.primary.Q15_FindKthToTail;

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @author: lynn
 * @Descript:  对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.
 * @date: 2021/6/15 22:49
 * @version: 1.0
 */
public class meituan22 {

    public static void main(String[] args) {


    }

    public static void reorderList(ListNode head){
        if (head==null ) return;
        ListNode slowNode=head;
        ListNode fastNode=head;
        while (fastNode.next!=null && fastNode.next.next==null){
            fastNode =fastNode.next.next;
            slowNode=slowNode.next;
        }
        ListNode halfNode=slowNode.next;
        ListNode pre=null;
        slowNode.next=null;
        while (halfNode!=null){
            ListNode tmpNode=halfNode.next;
            halfNode.next=pre;
            pre=halfNode;
            halfNode=tmpNode;
        }
        ListNode firstNode=head;
        ListNode afterNode=pre;
        while (firstNode!=null && afterNode!=null){
            ListNode fNext=fastNode.next;
            ListNode aNext=afterNode.next;
            firstNode.next=afterNode;
            afterNode.next=fNext;
            fastNode=fNext;
            afterNode=aNext;
        }
    }


    private static  class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val=val;
        }
    }

}
